#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TREE_SIZE 100  // 定义最大的树的大小
#define MAX_CHAR 256       // 假定字符集的大小最多256个可能的字符

typedef struct {
    int weight;            // 节点的权重
    int parent, lchild, rchild;  // 父节点、左子节点、右子节点的索引
} HuffmanNode, HuffmanTree[MAX_TREE_SIZE];

typedef char *HuffmanCode[MAX_CHAR];  // 哈夫曼编码的类型

// 选择两个最小权重的未合并的节点
void selectMin(HuffmanTree tree, int n, int *s1, int *s2) {
    *s1 = *s2 = 0;  // 初始化两个最小节点索引
    for (int i = 1; i <= n; i++) {
        if (tree[i].parent == 0 && (*s1 == 0 || tree[i].weight < tree[*s1].weight)) {
            *s2 = *s1;  // 更新次小值
            *s1 = i;    // 更新最小值
        } else if (tree[i].parent == 0 && (*s2 == 0 || tree[i].weight < tree[*s2].weight)) {
            *s2 = i;
        }
    }
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree tree, int weights[], int n) {
    if (n <= 1) return;  // 如果只有一个字符，不需要构建树
    int m = 2 * n - 1;   // 计算总节点数
    for (int i = 1; i <= m; ++i) {
        tree[i].parent = tree[i].lchild = tree[i].rchild = 0;  // 初始化树节点
    }
    for (int i = 1; i <= n; ++i) {
        tree[i].weight = weights[i - 1];  // 加载叶子节点的权重
    }//初始化
    for (int i = n + 1; i <= m; ++i) {
        int s1, s2;
        selectMin(tree, i - 1, &s1, &s2);  // 选择两个最小的节点
        tree[s1].parent = tree[s2].parent = i;  // 设置选中节点的父节点
        tree[i].lchild = s1;  // 设置新节点的左子节点
        tree[i].rchild = s2;  // 设置新节点的右子节点
        tree[i].weight = tree[s1].weight + tree[s2].weight;  // 更新新节点的权重
    }
}

// 从构建好的哈夫曼树生成哈夫曼编码
void generateHuffmanCodes(HuffmanTree tree, HuffmanCode hCodes, int n) {
    char *code = (char *)malloc(n * sizeof(char));
    code[n - 1] = '\0';  // 字符串结束符
    for (int i = 1; i <= n; i++) {
        int start = n - 1;  // 从下往上回溯
        for (int c = i, p = tree[i].parent; p != 0; c = p, p = tree[p].parent) {//起始条件：c 为叶子字符，p 为其父节； 中指条件：p == 0 根节点； 循环条件 c 为父节点， p 为父节点的父节点
            if (tree[p].lchild == c) code[--start] = '0';  // 左孩子为0， 存储到高位地址
            else code[--start] = '1';  // 右孩子为1，存储到高位地址
        }
        hCodes[i] = (char *)malloc((n - start) * sizeof(char));  // 分配内存存储编码
        strcpy(hCodes[i], &code[start]);  // 复制编码字符串
    }
    free(code);  // 释放临时字符串内存
}

// 主函数
int main() {
    int weights[] = {5, 29, 7, 8, 14, 23, 3, 11};  // 字符的权重
    int n = sizeof(weights) / sizeof(weights[0]);  // 字符的数量
    HuffmanTree tree;
    HuffmanCode hCodes;

    createHuffmanTree(tree, weights, n);  // 构建哈夫曼树
    generateHuffmanCodes(tree, hCodes, n);  // 生成哈夫曼编码

    for (int i = 1; i <= n; i++) {
        printf("Char %d: Code = %s\n", i, hCodes[i]);  // 打印字符及其对应的哈夫曼编码
    }

    return 0;
}
